home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / OTHERCST / JPSRC_FO / JQUANT1.C < prev    next >
Text File  |  1991-10-13  |  13KB  |  388 lines
  1. /*
  2.  * jquant1.c
  3.  *
  4.  * Copyright (C) 1991, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains 1-pass color quantization (color mapping) routines.
  9.  * These routines are invoked via the methods color_quantize
  10.  * and color_quant_init/term.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15. #ifdef QUANT_1PASS_SUPPORTED
  16.  
  17.  
  18. /*
  19.  * This implementation is a fairly dumb, quick-and-dirty quantizer;
  20.  * it's here mostly so that we can start working on colormapped output formats.
  21.  *
  22.  * We quantize to a color map that is selected in advance of seeing the image;
  23.  * the map depends only on the requested number of colors (at least 8).
  24.  * The map consists of all combinations of Ncolors[j] color values for each
  25.  * component j; we choose Ncolors[] based on the requested # of colors.
  26.  * We always use 0 and MAXJSAMPLE in each color (hence the minimum 8 colors).
  27.  * Any additional color values are equally spaced between these limits.
  28.  *
  29.  * The result almost always needs dithering to look decent.
  30.  */
  31.  
  32. #define MAX_COMPONENTS 4    /* max components I can handle */
  33.  
  34. static int total_colors;    /* Number of distinct output colors */
  35. static int Ncolors[MAX_COMPONENTS]; /* # of values alloced to each component */
  36. /* total_colors is the product of the Ncolors[] values */
  37.  
  38. static JSAMPARRAY colormap;    /* The actual color map */
  39. /* colormap[i][j] = value of i'th color component for output pixel value j */
  40.  
  41. static JSAMPARRAY colorindex;    /* Precomputed mapping for speed */
  42. /* colorindex[i][j] = index of color closest to pixel value j in component i,
  43.  * premultiplied so that the correct mapped value for a pixel (r,g,b) is:
  44.  *   colorindex[0][r] + colorindex[1][g] + colorindex[2][b]
  45.  */
  46.  
  47.  
  48. /* Declarations for Floyd-Steinberg dithering.
  49.  * Errors are accumulated into the arrays evenrowerrs[] and oddrowerrs[],
  50.  * each of which have #colors * (#columns + 2) entries (so that first/last
  51.  * pixels need not be special cases).  These have resolutions of 1/16th of
  52.  * a pixel count.  The error at a given pixel is propagated to its unprocessed
  53.  * neighbors using the standard F-S fractions,
  54.  *        ...    (here)    7/16
  55.  *        3/16    5/16    1/16
  56.  * We work left-to-right on even rows, right-to-left on odd rows.
  57.  *
  58.  * Note: on a wide image, we might not have enough room in a PC's near data
  59.  * segment to hold the error arrays; so they are allocated with alloc_medium.
  60.  */
  61.  
  62. #ifdef EIGHT_BIT_SAMPLES
  63. typedef short FSERROR;        /* 16 bits should be enough */
  64. #else
  65. typedef INT32 FSERROR;        /* may need more than 16 bits? */
  66. #endif
  67.  
  68. typedef FSERROR FAR *FSERRPTR;    /* pointer to error array (in FAR storage!) */
  69.  
  70. static FSERRPTR evenrowerrs, oddrowerrs; /* current-row and next-row errors */
  71. static boolean on_odd_row;    /* flag to remember which row we are on */
  72.  
  73.  
  74. /*
  75.  * Initialize for one-pass color quantization.
  76.  */
  77.  
  78. METHODDEF void
  79. color_quant_init (decompress_info_ptr cinfo)
  80. {
  81.   int max_colors = cinfo->desired_number_of_colors;
  82.   int i,j,k, ntc, nci, blksize, blkdist, ptr, val;
  83.  
  84.   if (cinfo->color_out_comps > MAX_COMPONENTS)
  85.     ERREXIT1(cinfo->emethods, "Cannot quantize more than %d color components",
  86.          MAX_COMPONENTS);
  87.   if (max_colors > (MAXJSAMPLE+1))
  88.     ERREXIT1(cinfo->emethods, "Cannot request more than %d quantized colors",
  89.         MAXJSAMPLE+1);
  90.  
  91.   /* Initialize to 2 color values for each component */
  92.   total_colors = 1;
  93.   for (i = 0; i < cinfo->color_out_comps; i++) {
  94.     Ncolors[i] = 2;
  95.     total_colors *= 2;
  96.   }
  97.   if (total_colors > max_colors)
  98.     ERREXIT1(cinfo->emethods, "Cannot quantize to fewer than %d colors",
  99.          total_colors);
  100.  
  101.   /* Increase the number of color values until requested limit is reached. */
  102.   /* Note that for standard RGB color space, we will have at least as many */
  103.   /* red values as green, and at least as many green values as blue. */
  104.   i = 0;            /* component index to increase next */
  105.   /* test calculates ntc = new total_colors if Ncolors[i] is incremented */
  106.   while ((ntc = (total_colors / Ncolors[i]) * (Ncolors[i]+1)) <= max_colors) {
  107.     Ncolors[i]++;        /* OK, apply the increment */
  108.     total_colors = ntc;
  109.     i++;            /* advance to next component */
  110.     if (i >= cinfo->color_out_comps) i = 0;
  111.   }
  112.  
  113.   /* Report selected color counts */
  114.   if (cinfo->color_out_comps == 3)
  115.     TRACEMS4(cinfo->emethods, 1, "Quantizing to %d = %d*%d*%d colors",
  116.          total_colors, Ncolors[0], Ncolors[1], Ncolors[2]);
  117.   else
  118.     TRACEMS1(cinfo->emethods, 1, "Quantizing to %d colors", total_colors);
  119.  
  120.   /* Allocate and fill in the colormap and color index. */
  121.   /* The colors are ordered in the map in standard row-major order, */
  122.   /* i.e. rightmost (highest-indexed) color changes most rapidly. */
  123.  
  124.   colormap = (*cinfo->emethods->alloc_small_sarray)
  125.         ((long) total_colors, (long) cinfo->color_out_comps);
  126.   colorindex = (*cinfo->emethods->alloc_small_sarray)
  127.         ((long) (MAXJSAMPLE+1), (long) cinfo->color_out_comps);
  128.  
  129.   /* blksize is number of adjacent repeated entries for a component */
  130.   /* blkdist is distance between groups of identical entries for a component */
  131.   blkdist = total_colors;
  132.  
  133.   for (i = 0; i < cinfo->color_out_comps; i++) {
  134.     /* fill in colormap entries for i'th color component */
  135.     nci = Ncolors[i];        /* # of distinct values for this color */
  136.     blksize = blkdist / nci;
  137.     for (j = 0; j < nci; j++) {
  138.       val = (j * MAXJSAMPLE + (nci-1)/2) / (nci-1); /* j'th value of color */
  139.       for (ptr = j * blksize; ptr < total_colors; ptr += blkdist) {
  140.     /* fill in blksize entries beginning at ptr */
  141.     for (k = 0; k < blksize; k++)
  142.       colormap[i][ptr+k] = val;
  143.       }
  144.     }
  145.     blkdist = blksize;        /* blksize of this color is blkdist of next */
  146.  
  147.     /* fill in colorindex entries for i'th color component */
  148.     for (j = 0; j <= MAXJSAMPLE; j++) {
  149.       /* compute index of color closest to pixel value j */
  150.       val = (j * (nci-1) + CENTERJSAMPLE) / MAXJSAMPLE;
  151.       /* premultiply so that no multiplication needed in main processing */
  152.       val *= blksize;
  153.       colorindex[i][j] = val;
  154.     }
  155.   }
  156.  
  157.   /* Pass the colormap to the output module.  Note that the output */
  158.   /* module is allowed to save this pointer and use the map during */
  159.   /* any put_pixel_rows call! */
  160.   (*cinfo->methods->put_color_map) (cinfo, total_colors, colormap);
  161.  
  162.   /* Allocate Floyd-Steinberg workspace if necessary */
  163.   if (cinfo->use_dithering) {
  164.     size_t arraysize = (cinfo->image_width + 2L) * cinfo->color_out_comps
  165.                * SIZEOF(FSERROR);
  166.  
  167.     evenrowerrs = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize);
  168.     oddrowerrs  = (FSERRPTR) (*cinfo->emethods->alloc_medium) (arraysize);
  169.     /* we only need to zero the forward contribution for current row. */
  170.     jzero_far((void FAR *) evenrowerrs, arraysize);
  171.     on_odd_row = FALSE;
  172.   }
  173.  
  174. }
  175.  
  176.  
  177. /*
  178.  * Map some rows of pixels to the output colormapped representation.
  179.  */
  180.  
  181. METHODDEF void
  182. color_quantize (decompress_info_ptr cinfo, int num_rows,
  183.         JSAMPIMAGE input_data, JSAMPARRAY output_data)
  184. /* General case, no dithering */
  185. {
  186.   register int pixcode, ci;
  187.   register long col;
  188.   register int row;
  189.   register long widthm1 = cinfo->image_width - 1;
  190.   register int nc = cinfo->color_out_comps;  
  191.  
  192.   for (row = 0; row < num_rows; row++) {
  193.     for (col = widthm1; col >= 0; col--) {
  194.       pixcode = 0;
  195.       for (ci = 0; ci < nc; ci++) {
  196.     pixcode += GETJSAMPLE(colorindex[ci]
  197.                   [GETJSAMPLE(input_data[ci][row][col])]);
  198.       }
  199.       output_data[row][col] = pixcode;
  200.     }
  201.   }
  202. }
  203.  
  204.  
  205. METHODDEF void
  206. color_quantize3 (decompress_info_ptr cinfo, int num_rows,
  207.          JSAMPIMAGE input_data, JSAMPARRAY output_data)
  208. /* Fast path for color_out_comps==3, no dithering */
  209. {
  210.   register int pixcode;
  211.   register JSAMPROW ptr0, ptr1, ptr2, ptrout;
  212.   register long col;
  213.   register int row;
  214.   register long width = cinfo->image_width;
  215.  
  216.   for (row = 0; row < num_rows; row++) {
  217.     ptr0 = input_data[0][row];
  218.     ptr1 = input_data[1][row];
  219.     ptr2 = input_data[2][row];
  220.     ptrout = output_data[row];
  221.     for (col = width; col > 0; col--) {
  222.       pixcode  = GETJSAMPLE(colorindex[0][GETJSAMPLE(*ptr0++)]);
  223.       pixcode += GETJSAMPLE(colorindex[1][GETJSAMPLE(*ptr1++)]);
  224.       pixcode += GETJSAMPLE(colorindex[2][GETJSAMPLE(*ptr2++)]);
  225.       *ptrout++ = pixcode;
  226.     }
  227.   }
  228. }
  229.  
  230.  
  231. METHODDEF void
  232. color_quantize_dither (decompress_info_ptr cinfo, int num_rows,
  233.                JSAMPIMAGE input_data, JSAMPARRAY output_data)
  234. /* General case, with Floyd-Steinberg dithering */
  235. {
  236.   register int pixcode, ci;
  237.   register FSERROR val;
  238.   register FSERRPTR thisrowerr, nextrowerr;
  239.   register long col;
  240.   register int row;
  241.   register long width = cinfo->image_width;
  242.   register int nc = cinfo->color_out_comps;  
  243.  
  244.   for (row = 0; row < num_rows; row++) {
  245.     if (on_odd_row) {
  246.       /* work right to left in this row */
  247.       thisrowerr = oddrowerrs + width*nc;
  248.       nextrowerr = evenrowerrs + width*nc;
  249.       for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */
  250.     nextrowerr[ci] = 0;
  251.       for (col = width - 1; col >= 0; col--) {
  252.     /* select the output pixel value */
  253.     pixcode = 0;
  254.     for (ci = 0; ci < nc; ci++) {
  255.       /* compute pixel value + accumulated error */
  256.       val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4)
  257.         + thisrowerr[ci];
  258.       if (val < 0) val = 0;    /* must watch for range overflow! */
  259.       else {
  260.         val += 8;        /* divide by 16 with proper rounding */
  261.         val >>= 4;
  262.         if (val > MAXJSAMPLE) val = MAXJSAMPLE;
  263.       }
  264.       thisrowerr[ci] = val;    /* save for error propagation */
  265.       pixcode += GETJSAMPLE(colorindex[ci][val]);
  266.     }
  267.     output_data[row][col] = pixcode;
  268.     /* propagate error to adjacent pixels */
  269.     for (ci = 0; ci < nc; ci++) {
  270.       val = thisrowerr[ci] - GETJSAMPLE(colormap[ci][pixcode]);
  271.       thisrowerr[ci-nc] += val * 7;
  272.       nextrowerr[ci+nc] += val * 3;
  273.       nextrowerr[ci   ] += val * 5;
  274.       nextrowerr[ci-nc]  = val; /* not +=, since not initialized yet */
  275.     }
  276.     thisrowerr -= nc;    /* advance error ptrs to next pixel entry */
  277.     nextrowerr -= nc;
  278.       }
  279.       on_odd_row = FALSE;
  280.     } else {
  281.       /* work left to right in this row */
  282.       thisrowerr = evenrowerrs + nc;
  283.       nextrowerr = oddrowerrs + nc;
  284.       for (ci = 0; ci < nc; ci++) /* need only initialize this one entry */
  285.     nextrowerr[ci] = 0;
  286.       for (col = 0; col < width; col++) {
  287.     /* select the output pixel value */
  288.     pixcode = 0;
  289.     for (ci = 0; ci < nc; ci++) {
  290.       /* compute pixel value + accumulated error */
  291.       val = (((FSERROR) GETJSAMPLE(input_data[ci][row][col])) << 4)
  292.         + thisrowerr[ci];
  293.       if (val < 0) val = 0;    /* must watch for range overflow! */
  294.       else {
  295.         val += 8;        /* divide by 16 with proper rounding */
  296.         val >>= 4;
  297.         if (val > MAXJSAMPLE) val = MAXJSAMPLE;
  298.       }
  299.       thisrowerr[ci] = val;    /* save for error propagation */
  300.       pixcode += GETJSAMPLE(colorindex[ci][val]);
  301.     }
  302.     output_data[row][col] = pixcode;
  303.     /* propagate error to adjacent pixels */
  304.     for (ci = 0; ci < nc; ci++) {
  305.       val = thisrowerr[ci] - GETJSAMPLE(colormap[ci][pixcode]);
  306.       thisrowerr[ci+nc] += val * 7;
  307.       nextrowerr[ci-nc] += val * 3;
  308.       nextrowerr[ci   ] += val * 5;
  309.       nextrowerr[ci+nc]  = val; /* not +=, since not initialized yet */
  310.     }
  311.     thisrowerr += nc;    /* advance error ptrs to next pixel entry */
  312.     nextrowerr += nc;
  313.       }
  314.       on_odd_row = TRUE;
  315.     }
  316.   }
  317. }
  318.  
  319.  
  320. /*
  321.  * Finish up at the end of the file.
  322.  */
  323.  
  324. METHODDEF void
  325. color_quant_term (decompress_info_ptr cinfo)
  326. {
  327.   /* We can't free the colormap until now, since output module may use it! */
  328.   (*cinfo->emethods->free_small_sarray)
  329.         (colormap, (long) cinfo->color_out_comps);
  330.   (*cinfo->emethods->free_small_sarray)
  331.         (colorindex, (long) cinfo->color_out_comps);
  332.   if (cinfo->use_dithering) {
  333.     (*cinfo->emethods->free_medium) ((void FAR *) evenrowerrs);
  334.     (*cinfo->emethods->free_medium) ((void FAR *) oddrowerrs);
  335.   }
  336. }
  337.  
  338.  
  339. /*
  340.  * Prescan some rows of pixels.
  341.  * Not used in one-pass case.
  342.  */
  343.  
  344. METHODDEF void
  345. color_quant_prescan (decompress_info_ptr cinfo, int num_rows,
  346.              JSAMPIMAGE image_data)
  347. {
  348.   ERREXIT(cinfo->emethods, "Should not get here!");
  349. }
  350.  
  351.  
  352. /*
  353.  * Do two-pass quantization.
  354.  * Not used in one-pass case.
  355.  */
  356.  
  357. METHODDEF void
  358. color_quant_doit (decompress_info_ptr cinfo, quantize_caller_ptr source_method)
  359. {
  360.   ERREXIT(cinfo->emethods, "Should not get here!");
  361. }
  362.  
  363.  
  364. /*
  365.  * The method selection routine for 1-pass color quantization.
  366.  */
  367.  
  368. GLOBAL void
  369. jsel1quantize (decompress_info_ptr cinfo)
  370. {
  371.   if (! cinfo->two_pass_quantize) {
  372.     cinfo->methods->color_quant_init = color_quant_init;
  373.     if (cinfo->use_dithering) {
  374.       cinfo->methods->color_quantize = color_quantize_dither;
  375.     } else {
  376.       if (cinfo->color_out_comps == 3)
  377.     cinfo->methods->color_quantize = color_quantize3;
  378.       else
  379.     cinfo->methods->color_quantize = color_quantize;
  380.     }
  381.     cinfo->methods->color_quant_prescan = color_quant_prescan;
  382.     cinfo->methods->color_quant_doit = color_quant_doit;
  383.     cinfo->methods->color_quant_term = color_quant_term;
  384.   }
  385. }
  386.  
  387. #endif /* QUANT_1PASS_SUPPORTED */
  388.